Greedy Particle Swarm Algorithms for Multidimensional Knapsack Problems

doi:10.3969/j.issn.1006-2475.2011.06.024

Computer and Modernization ›› 2011, Vol. 1 ›› Issue (6): 83-5.doi: 10.3969/j.issn.1006-2475.2011.06.024

• 算法分析与设计 • Previous Articles Next Articles

Greedy Particle Swarm Algorithms for Multidimensional Knapsack Problems

HAO Jun-ling

School of Information Technology & Management Engineering, University of International Business and Economics, Beijing 100029, China

Received:2011-03-28 Revised:1900-01-01 Online:2011-06-29 Published:2011-06-29

Abstract

Abstract: Two new greedy transformations and the inspired algorithms are proposed to solve multidimensional knapsack problems (MKP01) with weight and volume constraints. Convex combination and infinite norm of the ratio vectors of performance to weight and performance to volume are computed and two integrative "performanceprice ratio" vectors are obtained. Two greedy PSOs variants (wPSO: weighted PSO, infPSO: infinite norm PSO) are presented for MKP01 based on the integrative "performanceprice ratio". The standard PSO, hybrid wPSO and infPSO are applied to solve various scales of MKP instances. Numerical experiments illustrate that wPSO and infPSO not only outperform PSO greatly, but also show excellent and steady searching abilities and encouraging efficiency to locate the optimal solutions.

Key words: multidimensional knapsack problem, particle swarm optimization, greedy transformation, integrative performanceprice ratio

HAO Jun-ling. Greedy Particle Swarm Algorithms for Multidimensional Knapsack Problems[J]. Computer and Modernization, 2011, 1(6): 83-5.

[1]	MAO Ming-yang, XU Sheng-chao. Continuous Attribute Discretization Algorithm of Rough Sets for BP Neural Networks Based on Particle Swarm Optimization#br# [J]. Computer and Modernization, 2023, 0(09): 115-119.
[2]	HAN Xue. Multi Path Planning Based on Constrained Clustering and Particle Swarm Optimization [J]. Computer and Modernization, 2023, 0(08): 7-11.
[3]	PAN Si-yuan, ZHANG Wei. SOC Estimation of Lithium Battery Based on Improved LSTM [J]. Computer and Modernization, 2023, 0(08): 25-30.
[4]	LIU Fu-qi, ZHANG Da. PSO-DBN-based Hydraulic System Cooler Fault Diagnosis [J]. Computer and Modernization, 2023, 0(06): 7-14.
[5]	PAN Yu-qing, ZHANG Su-ning, FENG Ren-jun, JING Dong-sheng. Intrusion Detection Method Based on Particle Swarm Optimization Combined with LightGBM [J]. Computer and Modernization, 2023, 0(04): 123-126.
[6]	ZENG Yi-pu, DAI Yi-ru, CHEN Yu-tian. Dynamic Particle Swarm Optimization without Velocity Based on Opposition-based Learning and Elite Promotion [J]. Computer and Modernization, 2023, 0(03): 113-120.
[7]	LIU Ya-wen, JIANG Yan, PAN Da-zhi. Improved Binary Harmony Search Algorithm for Solving Multidimensional Knapsack Problem [J]. Computer and Modernization, 2022, 0(08): 13-19.
[8]	HUANG Ling, BAI Xiao-bo. Teachers’ Scientific Research Performance Prediction Based on PSO-KPLS [J]. Computer and Modernization, 2022, 0(06): 8-12.
[9]	LIU Zhi-feng, SHU Zhi-hao, XU Yue-feng, YANG Shu-yi, SHEN Wen-long. Artificial Fish Swarm Algorithm Based on PSO Adaptive Dual Strategy [J]. Computer and Modernization, 2022, 0(05): 46-53.
[10]	ZHANG Yan-hu, YAN Li-juan, MA Zhi-fen, ZHANG Yan-jun. An improved Particle Swarm Optimization (PSO) Force Unloading Algorithm for Multi-task and Multi-resource Moving Edge Computing Environment [J]. Computer and Modernization, 2022, 0(05): 54-60.
[11]	LI Ling, CHEN Xi, SHEN Wei-jie, XIONG Han-wu, CAI Ran-ran. An Edge Caching Strategy for Intelligent Manufacturing Supervision of Electrical Equipment [J]. Computer and Modernization, 2022, 0(05): 61-67.
[12]	LIANG Zheng-you , , WANG Lu , LI Xuan-ang , YANG Feng , . A Point Cloud Registration Algorithm Combining Improved PSO Algorithm and TrICP Algorithm [J]. Computer and Modernization, 2022, 0(05): 90-95.
[13]	WANG Zhe, WANG Long-da, LIU GANG, WANG Xing-cheng, WANG Zhong-jun, BAO Lu-jie. Improved Immune Particle Swarm Optimization Algorithm for Automatic Parallel Parking Based on Cubic Spline Interpolation#br# [J]. Computer and Modernization, 2022, 0(02): 7-12.
[14]	GUO Cheng, ZHANG Wan-da, WANG Bo, WANG Jia-fu. Particle Swarm Optimization Algorithm Based on Multigroup Parallel Cooperation [J]. Computer and Modernization, 2022, 0(01): 33-40.
[15]	CHEN Xiang, ZOU Qing-nian, XIE Shao-yu, CHEN Cui-qiong. Identification of Platen Switch State Based on Transfer Learning Strategy [J]. Computer and Modernization, 2021, 0(05): 120-126.

Greedy Particle Swarm Algorithms for Multidimensional Knapsack Problems

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments